package cn.com.colasoft.dataStructure;

/**
 * https://www.baeldung.com/java-quicksort
 * 时间复杂度nlogn
 */
public class QuickSort {

    private int partition(int arr[], int begin, int end) {
        // 选取一个pivot值，所有比pivot值大的值放在右边，所有比pivot值小的放在左边
        int pivot = arr[end];
        int i = (begin-1);

        for (int j = begin; j < end; j++) {
            if (arr[j] <= pivot) {
                i++;

                int swapTemp = arr[i];
                arr[i] = arr[j];
                arr[j] = swapTemp;
            }
        }

        int swapTemp = arr[i+1];
        arr[i+1] = arr[end];
        arr[end] = swapTemp;

        return i+1;
    }

    public void quickSort(int arr[], int begin, int end) {
        if (begin < end) {
            int partitionIndex = partition(arr, begin, end);

            quickSort(arr, begin, partitionIndex-1);
            quickSort(arr, partitionIndex+1, end);
        }
    }

    public static void main(String[] args) {
        int[] arry = new int[]{6, 2, 1, 3, 5, 1};
        new QuickSort().quickSort(arry, 0, arry.length - 1);
        for (int item : arry) {
            System.out.print(item + " ");
        }
    }

}